1. Technical Field
The invention relates to a distributed computing environment. More particularly, the invention relates to a method and apparatus for fair-share preemption of processes executed in a distributed computing environment.
2. Discussion of the Prior Art
Companies are increasingly using compute farms to efficiently perform the vast amount of computing tasks and services that are necessary to deliver increased computing capacity to their users. For purposes of the discussion herein, a compute farm is defined as a group of networked servers or, alternatively, as a networked multi-processor computing environment, in which work is distributed between multiple processors. The major components of the compute farm architecture include applications, central processors (CPUs) and memory resources, operating systems, a network infrastructure, a data storage infrastructure, load-sharing and scheduling mechanisms, in addition to means for monitoring and tuning the compute farm. A compute farm provides for more efficient processing by distributing the workload between individual components or processors of the farm and, thereby, execution of computing processes is expedited by using the available power of multiple processors.
Compute farms are usually coupled with a layer of a distributed resource management (DRM) system that is used for load-sharing between resources of the farm. The DRM performs numerous tasks, such as tracking processes' demand, selecting machines on which to run a given task or process, and prioritizing, as well as scheduling tasks for execution. Examples of DRM systems are the load-sharing facility (LSF) provided by Platform Computing™, OpenPBS, FT/NC® provided by Runtime Design Automation, and the like.
Resources are managed according to predefined policies to share the workload in a compute farm. These policies can be determined based on the number of CPUs, licenses, memory constraints, job priorities, duration of jobs, and so on. A set of queues is provided to fulfill the policies and efficiently manage the resources thus allowing the submission of jobs. A queue may be parameterized, for example, according to a scheduling priority, a number of jobs per user, a maximum run time of a job from that queue, an amount of memory that a job from that queue is expected to use, or any combination thereof. For example, the higher the scheduling priority of the queue, the stricter the resource limit on that queue. In contrast, a low priority queue might allow hundreds of concurrent jobs. However, these jobs can be preempted by jobs arriving from a higher priority queue. Regardless to the select policy, resources should be managed on a fair-share basis. Such fairness prevents starvation for computing resources of other users when one user has submitted a set of jobs that would consume all available job slots.
Many compute farm environments are capable of preempting computing resources, as required by applications executed on the farm. However, the shortcoming of prior art DRM solutions is the inability of such systems to preempt jobs while assuring fairness. As one example, a LSF system supports the preemption of low-priority jobs by high-priority jobs. That is, the LSF system preempts, i.e. suspends or terminates, lower-priority jobs if there is a scarcity of available recourses, and activates high-priority jobs. As a result, over time, a preempted low-priority job may always belong to the same user, instead of being a fair choice among all users who have low-priority jobs. Other preemption approaches, e.g. ownership based preemption, may be found in the related art and they similarly ignore the issue of fairness.
In view of the above, it would be, advantageous to provide a solution for preempting jobs while assuring fairness.